#include "main/utils.h"
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
      int len = nums.size();
      int ans = nums[0];
      int pre = nums[0];
      for (int i = 1; i < len; ++i) {
        pre = max(pre + nums[i], nums[i]);
        ans = max(pre, ans);
      }
      return ans;
    }

    struct status {
      int lsum, rsum, msum, isum;
    };
    status pushup(status lsub, status rsub) {
      int isum = lsub.isum + rsub.isum;
      int lsum = max(lsub.lsum, lsub.isum + rsub.lsum);
      int rsum = max(rsub.rsum, rsub.isum + lsub.rsum);
      int msum = max(max(lsub.msum, rsub.msum), lsub.rsum + rsub.lsum);
      return (status) {lsum, rsum, msum, isum};
    }
    status get(vector<int> &a, int l, int r) {
      if (l == r) {
        return (status){a[l], a[l], a[l], a[l]};
      }
      int m = (l + r) >> 1;
      auto lsub = get(a, l, m);
      auto rsub = get(a, m + 1, r);
      return pushup(lsub, rsub);
    }
    int maxSubArray1(vector<int>& nums) {
      return get(nums, 0, nums.size() - 1).msum;
    }
};

int main() {
  vector<int> input = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
  Solution su;
  cout << su.maxSubArray(input) << endl;
  cout << su.maxSubArray1(input) << endl;
}
